package sortAlgorithm;

/**
 * @description: <a href="https://leetcode.cn/problems/sort-colors/description/">75. 颜色分类</a>
 * @author: zhaoyinglin
 * @date: 2024/3/7
 */
public class SortColors {

    public static void main(String[] args) {

        int[] nums = new int[]{2,0,2,1,1,0};

        System.out.println(nums);
    }

    class Solution {
        public void sortColors(int[] nums) {

            if (nums == null || nums.length == 0) {
                return;
            }

            quickSort(nums);

        }

        private void quickSort(int[] nums) {
            quickSort(nums, 0, nums.length);
        }

        private void quickSort(int[] nums, int left, int right) {
            if (left >= right) {
                return;
            }

            int p = partition(nums, left, right);
            quickSort(nums, left, p - 1);
            quickSort(nums, p + 1, right);
        }

        private int partition(int[] nums, int left, int right) {
            int i = left, j, p = right;

            for (j = left; j < right; j++) {
                if (nums[j] <= nums[p]) {
                    swap(nums, i, j);
                    i++;
                }
            }

            swap(nums, i, p);

            return i;
        }

        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }



}
